#!/usr/bin/env python3

"""
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
"""

class Solution:
    def combine(self, n, k):
        return [case for case in self._combine(n, k, 1)]

    def _combine(self, n, k, start_index):
        if start_index + k > n + 1:
            return
        if k == 1:
            for i in range(start_index, n + 1):
                yield [i]
        else:
            for i in range(start_index, n + 1):
                for case in self._combine(n, k - 1, i + 1):
                    case.insert(0, i)
                    yield case
                    
                

if __name__ == '__main__':
    s = Solution()
    result = s.combine(4, 2)
    print(f'result: {result}')
